package com.Dec_Forteen;

import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;

public class Solution805 {

    //默认为false
    boolean ans=false;
    //加起来得到这个和所需要的数组元素个数
    Map<Integer,Integer> map=new HashMap<>();
    public boolean splitArraySameAverage(int[] nums) {
        int sum=0;
        for (int num : nums) {
            sum += num;
        }
        for (int i = 0; i < nums.length; i++) {
            nums[i]=nums[i]*nums.length-sum;
        }
        //System.out.println(Arrays.toString(nums));
        //二分法进行操作
        dfs(nums,0,nums.length/2+1,0,0);
        dfs(nums,nums.length/2+1,nums.length,0,0);
        return ans;
    }

    void dfs(int[] nums,int left,int right,int sum,int cnt){
        if (left<=nums.length/2){
            map.put(sum,cnt);
        }
        if (left>nums.length/2&&map.containsKey(-sum)&&map.get(-sum)+cnt!=0&&map.get(-sum)+cnt!=nums.length){
            ans=true;
        }
        if (ans){
        }else if (left<right){ //背包问题，选与不选
            dfs(nums,left+1,right,sum+nums[left],cnt+1);
            dfs(nums,left+1,right,sum,cnt);
        }
    }

    public static void main(String[] args) {
        Solution805 solution805=new Solution805();
        System.out.println(solution805.splitArraySameAverage(new int[]{1,2,3,4,5,6,7,8}));
    }

}
